// https://www.lintcode.com/problem/special-palindrome-string/

public class Solution {
    /**
     * @param ambigram: A list of paired ambigram letter.
     * @param word: A string need to be judged.
     * @return: If it is special palindrome string, return true.
     */
    public boolean ispalindrome(List<String> ambigram, String word) {
        // write your code here.
        HashMap<Character, HashSet<Character>> map = new HashMap<>();
        for (String s : ambigram) {
            Character c1 = s.charAt(0), c2 = s.charAt(1);
            if (!map.containsKey(c1)) {
                map.put(c1, new HashSet<>());
                map.get(c1).add(c1);
            }
            map.get(c1).add(c2);
            if (!map.containsKey(c2)) {
                map.put(c2, new HashSet<>());
                map.get(c2).add(c2);
            }
            map.get(c2).add(c1);
        }
        for (int i = 0; i < word.length(); ++i) {
            Character c = word.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new HashSet());
                map.get(c).add(c);
            }
        }
        int i = 0, j = word.length() - 1;
        while (i < j) {
            Character ci = word.charAt(i), cj = word.charAt(j);
            if (ci != cj) {
                if (!intersect(map.get(ci), map.get(cj))) {
                    return false;
                }
            }
            ++i;
            --j;
        }
        return true;
    }
    
    protected boolean intersect(HashSet<Character> s1, HashSet<Character> s2) {
        for (Character c : s1) {
            if (s2.contains(c)) {
                return true;
            }
        }
        return false;
    }
}